package com.mystudy.leetcode.problem.tree.p_429;

import com.mystudy.leetcode.base.Node;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: infoalgorithm
 * @description: N叉树的层序遍历
 * @author: zhouzhilong
 * @create: 2019-07-24 10:21
 **/
public class Solution {

    /**
     * 土鳖做法：用父子队列来做，效率很低
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<Node> parentQueue = new LinkedList<>();
        Queue<Node> sonQueue = new LinkedList<>();
        parentQueue.offer(root);

        int index = 0;
        while (!parentQueue.isEmpty()) {
            Node cur = parentQueue.poll();

            while(result.size()<index+1){
                result.add(new ArrayList<Integer>());
            }
            result.get(index);
            List<Node> childrens = cur.children;
            for (Node children : childrens) {
                sonQueue.offer(children);
            }
            if (parentQueue.isEmpty()) {
                if (!sonQueue.isEmpty()) {
                    parentQueue = null;
                    parentQueue = sonQueue;
                    sonQueue = new LinkedList<>();
                    index++;
                }
            }
        }
        return result;
    }


    /**
     *　递归方式
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder2(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        levelOrder(root,0,result);
        return result;
    }


    private void levelOrder(Node node,int depth,List<List<Integer>> result){
        if(node == null){
            return;
        }

        if(depth+1>result.size()){
            result.add(new ArrayList<>());
        }
        result.get(depth).add(node.val);


        for (Node child : node.children) {
            levelOrder(child,depth+1,result);
        }
    }
}


